1. Field of the Invention
The present invention relates to a technique of determining collision between three-dimensional virtual objects.
2. Description of the Related Art
The progress of computer hardware, display technologies, and graphic processors is enabling advanced CG (Computer Graphics) expressions. Along with this, CG is also used in industrial applications such as CAD (Computer Aided Design), and CG images are becoming more complex. In the CG technologies, a collision determination function which calculates the physical behaviors and collision state between three-dimensional objects to not only ensure the reality of images but also express more real behaviors is regarded to be very important as the CG rendering performance improves.
The collision determination function calculates whether three-dimensional polygons which approximate three-dimensional objects collide against each other so that impossible behavior can be avoided to prevent the polygons from, e.g., getting into each other.
The collision determination function is used for, in the design field, e.g., making of a product prototype using CAD data, virtual trainings before existence of an actual machine, and virtual operation verification tests to check whether components collide against each other in operating design data. In the entertainment field, the collision determination function is used to provide real behaviors of CG objects in movies and games. In the robot field, the collision determination function is used for simulations for obstruction avoidance or a process of kinetic trajectory generation. That is, applications in many fields are expected.
Particularly in a system for presenting real-time experience, interactively reacting to a user's motion in synchronism with CG rendering and reflecting operations conforming the physical world on CG rendering in real time plays an important role for improving the user's feeling of participation. Hence, the collision determination function is very important. Such systems especially include VR (Virtual Reality) and MR (Mixed Reality).
The conventional collision determination technology fundamentally approximates a three-dimensional object to a three-dimensional polyhedron and divides the surface into a plurality of three-dimensional polygons included in the polyhedron. For all combinations of the divided polygons, the collision between the polygons is determined. In this method, When the number of polygons included in a three-dimensional polyhedron is n, the calculation cost of collision determination increases by n2. For this reason, in an interactive system such as MR or VR, it is very difficult to CG-render a detailed three-dimensional object created by CAD in real time while executing collision determination.
To cope with this problem, a method preprocesses three-dimensional polygons to, e.g., remove elements having no influence on collision determination, thereby speeding up the process (Christer Ericson, “Real-Time Collision Detection”, Morgan Kaufmann Publishing). This method obviates the necessity of collision determination operations for all polygons. The collision determination operation is executed by using minimum and necessary polygons, thereby speeding up the process. However, in determining collision of, e.g., long objects or an object passing through a hole, many faces may simultaneously contact each other, and it is therefore impossible to remove many polygons by the preprocess, resulting in a decrease in speed.
To prevent a decrease in calculation speed, a technique of creating three-dimensional polyhedron data with a small number of polygons in advance is often employed. Examples of this method are as follows.                Polygon reduction: After the vertex information of a three-dimensional polyhedron is optimized, the three-dimensional polyhedron is reconstructed, thereby reducing the number of polygons.        Detail level change: A condition is given to, e.g., remove a three-dimensional polyhedron of a screw or the like whose size is equal to or smaller than a threshold value or remove a hole with a diameter equal to or smaller than a threshold value, thereby reducing the detail level of each three-dimensional object. A three-dimensional polyhedron with a low detail level is separately created to decrease the number of polygons.        
The conventional collision determination cannot be executed in real time for a three-dimensional object having a high detail level and a lot of polygons. For a real-time operation, currently, the number of polygons is decreased by reducing the detail level.
In such a collision determination function, CG rendering preferably operates at 30 to 60 Hz especially in a highly interactive field such as VR or MR. There are also required an operation without delay of CG rendering caused by collision determination, and simultaneously, real-time collision determination corresponding to a user's interactive operation. The important challenge for this purpose is especially to increase the speed of collision determination operation.
The collision determination operation using the prior art has two problems.                The shape changes upon polygon reduction or detail level change. More specifically, if the shape changes, an error occurs in the collision determination result of a CG-rendered three-dimensional polyhedron so no accurate collision determination can be done.        It is necessary to create data for collision determination independently of data for CG rendering. More specifically, polygon reduction or detail level change requires to separately create data different from that for CG rendering. The data needs to be separately loaded to the memory.        